package org.review.algorithm.linkedlist;

import lombok.Data;
import lombok.NonNull;
import lombok.RequiredArgsConstructor;

public class Josepfu {

    public static void main(String[] args) {
        CircleSingleLinkedList circleList = new CircleSingleLinkedList();
        // circleList.addBody(125);
        // circleList.showBoy();
        circleList.countBody(2, 3, 20);

    }
}

class CircleSingleLinkedList {
    private Boy first = null;

    public void addBody(int num) {
        if (num <= 0) {
            System.out.println("数量输错！");
            return;
        }
        Boy cur = null;
        for (int i = 1; i <= num; i++) {
            if (first == null) {
                first = new Boy(i);
                cur = first;
                first.next = cur;
            } else {
                cur.next = new Boy(i);
                cur = cur.next;
                cur.next = first;
            }
        }
    }

    public void showBoy() {
        if (first == null) return;

        Boy cur = first;

        while (true) {
            System.out.printf("第%d个小孩的下一个小孩是%s\n", cur.no, cur.next);
            if (cur.next == first) break;
            cur = cur.next;
        }
    }

    public void countBody(int startNo, int countNum, int nums) {

        if (startNo > nums || countNum < 1) {
            System.out.println("参数错误 ！");
        }
        addBody(nums);
        //TODO 实现方式1，相比方式2，少个步骤
/*        Boy current = first.next;
        //TODO 调整到开始位置
        for (int i = 1; i < startNo-1; i++) {
            current = current.next;
            first = first.next;
        }
        //TODO 开始循环报数出圈，只剩一个boy
        while (first!= current) {

            for (int i = 0; i < countNum - 1; i++) {
                current = current.next;
                first = first.next;
            }
            System.out.printf("第%d个小孩出圈 下一个小孩是%s\n", current.no, current.next);
            current = current.next;
            first.next = current;
        }*/


        //TODO 实现方式2
      /*  //TODO 首先需要一个辅助节点，来帮助boy出列, 使helper。next = frist
        Boy helper = first;
        while (helper.next != first) {
            helper = helper.next;
        }

        //TODO 是开始节点指向startNo
        for (int i = 0; i < startNo - 1; i++) {
            helper = helper.next;
            first = first.next;
        }
        //TODO 循环出列  直到剩下一个boy
        while (helper != first) {

            for (int i = 0; i < countNum - 1; i++) {
                first = first.next;
                helper = helper.next;
            }
            //TODO 数到cuntNum后 出列
            System.out.printf("第%d个小孩出圈 下一个小孩是%s\n", first.no, first.next);
            first = first.next;
            helper.next = first;
        }*/

        //TODO 实现方式3 比以上实现更简单， 但是要注意，使用的出列是first.next
        for (int i = 0; i < startNo - 2; i++) {
            first = first.next;
        }
        //TODO 考虑的时候，这一步退出条件很重要，再一个是其他的调整两次就能写出来
        while (first.next != first) {
            for (int i = 0; i < countNum - 1; i++) {//TODO  这里为什么是2次 因为first.next=first.next.next出圈所以相当于一次计数
                first = first.next;
            }
            System.out.printf("第%d个小孩出圈 下一个小孩是%s\n", first.next.no, first.next.next);
            first.next = first.next.next;
        }
        System.out.printf("最后留在圈中的小孩编号%d \n", first.getNo());
    }
}

@RequiredArgsConstructor
@Data
class Boy {
    @NonNull int no;
    Boy next;

    @Override
    public String toString() {
        return "Boy{" + "no=" + no + '}';
    }
}